Convolutional encoding offers an approach to error control wherein an entire data stream is converted, regardless of its length, into a single code word. Wicker, Error Control Systems for Digital Communication and Storage, p. 264 (Prentice Hall, 1995). Convolutional encoding has traditionally been implemented with linear shift registers using parity based algorithms. A block diagram of a conventional rate-1/2 convolutional encoder is illustrated in FIG. 4. The rate of this encoder is established by the fact that the encoder outputs two bits for every input bit. Wicker at p. 265. The conventional convolutional encoder includes shift register 700, first AND gate 705 and second AND gate 710. Shift register 700 has a series of memory elements. A stream of input data to be encoded is input to shift register 700 With each successive bit input to shift register 700, selected memory elements of shift register 700 are tapped off at interconnections 702 and added at first AND gate 705 according to a fixed pattern, represented by polynomial go shown in equation (1) below: EQU g0(D)=1+D.sup.2 +D.sup.4 ( 1)
Wicker at p. 265-66. At interconnections 707, a different group of selected memory elements of shift register 700 are tapped off and added at second AND gate 710 according to another fixed pattern, represented by polynomial g1(D) shown in equation (2) below. EQU g1(D)=1+D.sup.1 +D.sup.2 +D.sup.3 +D.sup.4 ( 2)
Coded output data R0 and R1 represent the parity bits of g0 and g1, respectively.
Alternatively, the conventional convolutional encoder shown in FIG. 4 may be implemented in software. In a software implementation, the values g.sub.0 and g.sub.1 may be stored in a memory. Table 1 below shows pseudo code for implementing the conventional convolutional encoder in software.
TABLE 1 ______________________________________ BEGIN shift.sub.-- reg = (shift.sub.-- reg&lt; &lt;1) + new.sub.-- data.sub.-- bit; temp = shift.sub.-- reg & g0 if the parity of temp is even, r0 = 0; else r0 = 1; temp = shift.sub.-- reg & gi; if the parity of temp is even, r1 = 0; else r1 = 1; output r0, r1; new.sub.-- data.sub.-- bit = next.sub.-- bit; go to BEGIN ______________________________________
When this pseudo code is implemented in a DSP1600 available from Lucent Technologies, the parity based algorithm may take 5+3n cycles for a rate-1/n convolutional encoder where n is an integer. For example, a rate-1/2 convolutional encoder (n=2) uses 11 cycles to encode a bit. A rate-1/3 convolutional encoder (n=3) uses 14 cycles to encode a bit.
Alternatively, the bits may be encoded in a parallel encoding process. For example, a 16 bit word may be encoded in parallel. In this case, using a rate-1/2 convolutional encoder according to the IS-54 standard of the Telecommunications Industry Association, the DSP1600 encodes 96 bits in 938 cycles. In other words, a bit is encoded every 9.7 cycles on average. For rate-1/n encoders where n&gt;2, the parallel approach is not as efficient as the parity based algorithm described above. Moreover, the parallel algorithm assumes the inputs to be in a 16-bit word format which in many applications including applications using the IS-136 of the Telecommunications Industry Association, extra cycles are used to convert from the bit format. The extra cycles also make the parallel encoding process less efficient.